package leetcode;

import java.util.*;

/**
 * 给定一个没有重复数字的序列，返回其所有可能的全排列。
 * <p>
 * 示例:
 * <p>
 * 输入: [1,2,3]
 * 输出:
 * [
 * [1,2,3],
 * [1,3,2],
 * [2,1,3],
 * [2,3,1],
 * [3,1,2],
 * [3,2,1]
 * ]
 */
public class Code46 {
    public static void main(String[] args) {
        long time = System.currentTimeMillis();
        System.out.println(new Code46().permuteUnique(new int[]{
                2,2,1,1
        }));
        long time2 = System.currentTimeMillis();
        System.out.println(time2-time);
//        long time = System.currentTimeMillis();
//        System.out.println(new Code46().permuteUnique(new int[]{
//                1, 2, 3, 4, 5, 6, 7, 8, 9, 10
//        }));
//        long time2 = System.currentTimeMillis();
//        System.out.println(time2-time);
    }

    Set<List<Integer>> allList = new HashSet<>();
    Set<Integer> set = new HashSet<>();
    Stack<Integer> stack = new Stack<>();

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> re = new ArrayList<>(createNeedOne(nums));
        return re;
    }

    private Set<List<Integer>> createNeedOne(int[] nums) {
        for (int a = 0; a < nums.length; a++) {
            if (!set.contains(nums[a])) {
                set.add(nums[a]);
                stack.push(nums[a]);
                if (set.size() == nums.length) {
//                    allList.addAll();
                } else {
                    createNeedOne(nums);
                }
                set.remove(nums[a]);
                stack.pop();
            }
        }
        return allList;
    }

    public List<List<Integer>> permuteUnique3(int[] nums) {
        Set<List<Integer>> need = new HashSet<>();
        backTrack(nums,new ArrayList<>(),need,new boolean[nums.length]);
        List<List<Integer>> lists = new ArrayList<>(need);
        return lists;
    }
    public void backTrack(int[] nums, List<Integer> list, Set<List<Integer>> res,boolean[] used) {
        if (list.size() == nums.length) {
            res.add(new ArrayList<>(list));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if(used[i]){
                continue;
            }
            list.add(nums[i]);
            used[i]=true;
            backTrack(nums, list, res,used);
            used[i]=false;
            list.remove(list.size() - 1);
        }
    }



    Set<String> strings = new HashSet<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        Set<List<Integer>> result = new HashSet<List<Integer>>();
        backtrace(nums, result, 0);
        return new ArrayList<>(result);
    }

    public void backtrace(int[] nums, Set<List<Integer>> result, int i) {
        if (i == nums.length - 1) {
            List<Integer> temp = new ArrayList<>();
            for (int r : nums) {
                temp.add(r);
            }
            result.add(temp);
        }
        for (int j = i; j < nums.length; j++) {
            if(nums[i]!=nums[j]||i<=j) {
                swap(nums, i, j);
                backtrace(nums, result, i + 1);
                swap(nums, i, j);
            }
        }
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
